This paper establishes tight bounds on the best-case time-complexity of distributed atomic read/write storage implementations that tolerate worst-case conditions. We study asynchronous robust implementations where a writer and a set of reader processes (clients) access an atomic storage implemented over a set of $2t+b+1$ server processes of which $t$ can fail: $b$ of these can be malicious and the rest can fail by crashing. We define a {\em lucky} operation (read or write) as one that runs synchronously and without contention. We determine the exact conditions under which a {\em lucky} operation can be {\em fast}, namely expedited in one-communication round-trip with no data authentication. We show that every \emph{lucky} write (resp., read) can be \emph{fast} despite $f_w$ (resp., $f_r$) actual failures, if and only if $f_w + f_r \leq t - b$.
展开▼
机译：本文为可承受最坏情况的分布式原子读/写存储实现的最佳情况时间复杂性建立了严格的界限。我们研究异步健壮的实现，其中编写者和一组读取器进程（客户端）访问在一组$ 2t + b + 1 $服务器进程上实现的原子存储，其中$ t $可能会失败：其中$ b $可能是恶意软件，其余的可能因崩溃而失败。我们将{\ em lucky}操作（读或写）定义为同步运行且无竞争的操作。我们确定在{\ em lucky}操作下可以进行{\ em fast}操作的确切条件，即在没有数据身份验证的情况下一次通信往返加速。我们显示，尽管$ f_w $（resp。，$ f_r $）实际失败，但仅当$ f_w + f_r \ leq t-时，每个\ emph {lucky}写入（重复，读）都可以是\ emph {fast}。 b $。
展开▼
